//
// Created by 刘振舟 on 2024/3/18.
//


#include <stdbool.h>
#include <stdlib.h>
#include <string.h>

int removeDuplicates(int* nums, int numsSize){
    int slow = 0, fast = 0;
    while (fast < numsSize) {
        if (nums[slow] != nums[fast]) {
            nums[++slow] = nums[fast];
        }
        ++fast;
    }
    return slow + 1;
}



int removeElement(int* nums, int numsSize, int val){
    int slow = 0, fast = 0;
    while (fast < numsSize) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
        ++fast;
    }
    return slow;
}

void moveZeroes(int* nums, int numsSize){
    int slow = 0, fast = 0;
    while (slow < numsSize) {
        if (fast < numsSize) {
            if (nums[fast] != 0) {
                nums[slow++] = nums[fast];
            }
            ++fast;
        } else {
            nums[slow++] = 0;
        }
    }

}

int* twoSum(int* numbers, int numbersSize, int target, int* returnSize){
    int left = 0, right = numbersSize - 1;
    int* array = (int*)malloc(sizeof(int) * 2);
    *returnSize = 2;
    while (left < right) {
        int sum = numbers[left] + numbers[right];
        if (sum == target) {
            array[0] = left + 1;
            array[1] = right + 1;
            return array;
        } else if (sum > target) {
            --right;
        } else {
            ++left;
        }
    }
    array[0] = -1;
    array[1] = -1;
    return array;
}

void reverseString(char* s, int sSize){
    int left = 0, right = sSize - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}

char * substr(char* str, int start, int end) {
    int length = end - start + 1;
    char *res = (char *) malloc(length);
    for (int i = 0; i < end; ++i) {
        if (i < start) {
            continue;
        }
        res[i - start] = str[i];
    }
    res[length - 1] = '\0';
    return res;
}

size_t getStrLen(char * str) {
    return str ? strlen(str) : 0;
}
char* getPalindrome(char* str, int left, int right) {
    int length = getStrLen(str);
    while (left >= 0 && right < length && str[left] == str[right]) {
        --left;
        ++right;
    }
    return substr(str, left + 1, right);
}

char * longestPalindrome(char * s){
    char arr[] = {'\0'};
    char *res = arr;
    for (int i = 0; i < getStrLen(s); ++i) {
        char* lStr = getPalindrome(s, i, i);
        char* rStr = getPalindrome(s, i, i + 1);
        res = getStrLen(lStr) > getStrLen(res) ? lStr : res;
        res = getStrLen(rStr) > getStrLen(res) ? rStr : res;
    }
    return res;
}

typedef struct {
    int* preSums;
} NumArray;


NumArray* numArrayCreate(int* nums, int numsSize) {
    NumArray* ptr = malloc(sizeof(NumArray));
    int* array = calloc(numsSize + 1, sizeof(int));
    array[0] = 0;
    for (int i = 1; i <= numsSize; ++i) {
        array[i] = array[i - 1] + nums[i - 1];
    }
    ptr->preSums = array;
    return ptr;
}

int numArraySumRange(NumArray* obj, int left, int right) {
    return obj->preSums[right + 1] - obj->preSums[left];
}

void numArrayFree(NumArray* obj) {
    free(obj->preSums);
    free(obj);
}


typedef struct {
    int **preSums;
    int rows;
    int cols;
} NumMatrix;


NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) {
    NumMatrix *numMatrix = malloc(sizeof(NumMatrix));
    numMatrix->rows = matrixSize + 1;
    numMatrix->cols = matrixColSize[0] + 1;
    int** sums = calloc(numMatrix->rows, sizeof(int *));
    for (int i = 0; i <= matrixSize; ++i) {
        sums[i] = calloc( numMatrix->cols, sizeof matrixSize);
    }
    for (int i = 1; i < numMatrix->rows; ++i) {
        for (int j = 1; j < numMatrix->cols; ++j) {
            sums[i][j] = sums[i - 1][j] + sums[i][j - 1] - sums[i - 1][j - 1] + matrix[i - 1][j - 1];
        }
    }
    numMatrix->preSums = sums;
    return numMatrix;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) {
    int** sums = obj->preSums;
    return sums[row2 + 1][col2 + 1] - sums[row2 + 1][col1] - sums[row1][col2 + 1] + sums[row1][col1];
}

void numMatrixFree(NumMatrix* obj) {
    for (int i = 0; i < obj->rows; ++i) {
        free(obj->preSums[i]);
    }
    free(obj->preSums);
    free(obj);
}

void diffIncrease(int* diff, const int* booking, int n){
    diff[booking[0] - 1] += booking[2];
    if (booking[1] < n) {
        diff[booking[1]] -= booking[2];
    }
}

int* diffResult(const int* diff, int n) {
    int* result = calloc(n, sizeof n);
    result[0] = diff[0];
    for (int i = 1; i < n; ++i) {
        result[i] = result[i - 1] + diff[i];
    }
    return result;
}

int* corpFlightBookings(int** bookings, int bookingsSize, int* bookingsColSize, int n, int* returnSize) {
    int* diff = calloc(n, sizeof n);
    for (int i = 0; i < bookingsSize; ++i) {
        diffIncrease(diff, bookings[i], n);
    }
    *returnSize = n;
    return diffResult(diff, n);
}

bool carPooling(int** trips, int tripsSize, int* tripsColSize, int capacity) {
    int toMax = 0;
    for (int i = 0; i < tripsSize; ++i) {
        toMax = (toMax > trips[i][2] ? toMax : trips[i][2]);
    }
    int stations = toMax + 1;
    int* diff = calloc(stations, sizeof tripsSize);
    for (int i = 0; i < tripsSize; ++i) {
        int* trip = trips[i];
        diff[trip[1]] += trip[0];
        diff[trip[2]] -= trip[0];
    }
    int people = 0;
    for (int i = 0; i < stations; ++i) {
        people += diff[i];
        if (people > capacity) {
            free(diff);
            return false;
        }
    }
    free(diff);
    return true;
}


void rotate(int** matrix, int matrixSize, int* matrixColSize) {
    for (int i = 0; i < matrixSize; ++i) {
        for (int j = 0; j < i; ++j) {
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }

    for (int i = 0; i < matrixSize; ++i) {
        int cols = matrixColSize[i];
        int start = 0, end = cols - 1;
        while (start < end) {
            int temp = matrix[i][start];
            matrix[i][start++] = matrix[i][end];
            matrix[i][end--] = temp;
        }
    }
}

int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize, int* returnSize) {
    int n = matrixColSize[0];
    int count = matrixSize * n;
    *returnSize = count;
    int leftBound = 0, upperBound = 0, rightBound = n - 1, bottomBound = matrixSize - 1;
    int* res = calloc(count, sizeof matrixSize);
    int index = 0;
    while (index < count) {
        if (upperBound <= bottomBound) {
            for (int i = leftBound; i <= rightBound; ++i) {
                res[index++] = matrix[upperBound][i];
            }
            ++upperBound;
        }
        if (leftBound <= rightBound) {
            for (int i = upperBound; i <= bottomBound; ++i) {
                res[index++] = matrix[i][rightBound];
            }
            --rightBound;
        }
        if (upperBound <= bottomBound) {
            for (int i = rightBound; i >= leftBound; --i) {
                res[index++] = matrix[bottomBound][i];
            }
            --bottomBound;
        }
        if (leftBound <= rightBound) {
            for (int i = bottomBound; i >= upperBound; --i) {
                res[index++] = matrix[i][leftBound];
            }
            ++leftBound;
        }
    }
    return res;
}

int main() {
    int numbers[] = {-1, 0};
    int returnSize = 2;
//    twoSum(numbers, 2, -1, &returnSize);

    int arr[3][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
    int cols[] = {3, 3, 3};
    int count;
    spiralOrder(arr, 3, cols, &count);
    // longestPalindrome("babad");
}